#include <iostream>
#include <queue>
#include <cstdio>

using namespace std;
#define MAX_N 1000005
int a[MAX_N];

int main(){

 //   freopen("2823.txt","r",stdin);

    int n,k;
    scanf("%d%d",&n,&k);
    for(int i = 0 ; i<n ; i++ ) scanf("%d",&a[i]);

    deque<int> que;

    for (int i = 0 ; i < k ; i++){
        while (!que.empty() && a[i] < a[que.back()]) que.pop_back();
        que.push_back(i);
    }
    cout <<a[que.front()];

    for (int i = k ; i < n ;i++){
        while(!que.empty() && i - que.front() >= k) que.pop_front();
        while(!que.empty() && a[i] < a[que.back()]) que.pop_back();
        que.push_back(i);
        cout << " "<< a[que.front()];
    }

    while (!que.empty()) que.pop_back();
    cout <<endl;

    for (int i = 0 ; i < k ; i++){
        while (!que.empty() && a[i] > a[que.back()]) que.pop_back();
        que.push_back(i);
    }
    cout <<a[que.front()];

    for (int i = k ; i < n ;i++){
        while(!que.empty() && i - que.front() >= k) que.pop_front();
        while(!que.empty() && a[i] > a[que.back()]) que.pop_back();
        que.push_back(i);
        cout << " "<< a[que.front()];
    }

    return 0;
}
